package Demo48;

/**
 * 归并排序复习
 * https://leetcode.cn/problems/sort-an-array/
 * 这个是和后续遍历差不多, 先取中间值,分制,递归,然后才排序
 */
class Solution {
    int[] ns;
    public int[] sortArray(int[] nums) {
        ns = new int[nums.length];
        mergeSort(nums, 0,nums.length - 1);
        return  nums;
    }

    private void mergeSort(int[] nums, int begin, int end) {
        if(begin >= end) {
            return;
        }
        // 取中
        int mid = (end - begin)/2;
        // 分治
        mergeSort(nums,begin,mid);
        mergeSort(nums,mid+1,begin);
        //
        int i = 0, left = begin, right = mid + 1;
        while(left <= mid && right <= end) {
            ns[i++] = nums[left] <= nums[right] ? nums[left++] : nums[right++];
        }

        while(left <= mid) {
            ns[i++] = nums[left++];
        }

        while(right <= end) {
            ns[i++] = nums[right++];
        }

        for(int j = begin; j <= end;j++) {
            nums[j] = ns[j - begin];
        }
    }
}